package leetcode;

import org.junit.Test;

/**
 * @author: feiwang_6
 * @create: 2020/7/19 14:31
 * @description: 
 */
public class 二分法和牛顿迭代法求平方根 {
    
    @Test
    public void test(){
        System.out.println(sqrtByTow(10, 0.00000001));
        
        System.out.println();
        
        System.out.println(sqrt(2, 0.00000001));
    }

    /**
     * 牛顿迭代法求解根号2的值
     * 构造一个数对序列 (A,B),(A+B, 2A+B)
     * @param ites
     * @return
     */
    public double sqrtByTow(int ites, double precision){
        double result = 0;
        int a = 1;
        int b = 1;
        for(int i = 1; i <= ites; i++){
            int oldA = a;
            a = a + b;
            b = 2*oldA + b;
            result = (b*1.0/a);
            if(Math.abs(result - 2) <= precision){
                break;
            }
        }
        return result;
    }

    /**
     * 二分法求根号m的值
     * @param m
     * @param precision  精确度
     * @return
     */
    public double sqrt(double m, double precision){
        double min = 1;
        double max = m;
        //二分寻找
        while(true){
            double middle = (min + max)/2;
            double re = middle * middle;
            if(Math.abs(re - m) <= precision){
                return middle;
            }
            //下一个最值
            if(re - m > 0){
                max = middle;
            }else {
                min = middle;
            }
        }
    }
}
